package com.peng.old.sort;


import com.peng.old.util.SortUtil;

/**
 * 归并排序
 */
public class MergeSort {
    public static void main(String[] args) {
        int[] arr = SortUtil.makeRandomArray(2000);

        sort(arr,0,arr.length-1);


        System.out.println(SortUtil.checkResult(arr));
    }

    /**
     * 将数组进行递归操作（操作内容：将数组分为左边和右边，对左边和右边进行排序，左右都排序好之后，进行归并操作）
     *
     * @param arr
     * @param left
     * @param right
     */
    public static void sort(int[] arr, int left, int right) {

        if (left == right) return;

        int midPos = left + (right - left) / 2;

        //左边排序
        sort(arr,left,midPos);

        //右边排序
        sort(arr,midPos+1,right);

        //归并
        merge(arr,left,midPos+1,right);


    }

    /**
     *  在左右两侧数组有序的前提下，进行归并排序操作（左侧数组一根指针i，右侧数组一根指针j，创建一个新的 存放有序的数组，并也赋予一根指针k）
     * @param arr
     * @param leftPos 左侧指针索引
     * @param rightPos 右侧指针索引
     * @param rightBound 右侧最大边界值
     */
    private static void merge(int[] arr, int leftPos, int rightPos, int rightBound) {
        int[] tempArr = new int[rightBound-leftPos+1];//存放有序的数组
        int midPos = rightPos-1;//中间索引
        int i = leftPos;
        int j = rightPos;
        int k = 0;
        while (i<=midPos && j<=rightBound){
            //等号是为了保证稳定性
            //这个过程可以比作是 格斗游戏的两个队伍 i组 和 j组 的人员分别进行出击对战（i，j分别比较），
            // 当一方的人输了(例如i<j，可看做是I组的人输了，那么便让i组的下一个人来进行作战（i的指针后移），反之亦是如此， 同时在下一个人作战（指针后移）之前，将输了的人放入休息室（新的数组里）
            tempArr[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
        }

        while (i<=midPos){
            tempArr[k++] = arr[i++];
        }

        while (j<=rightBound){
            tempArr[k++] = arr[j++];
        }
        for (int m = 0; m < tempArr.length; m++) {
            arr[leftPos+m] = tempArr[m];
        }


    }
}
